1715 카드 정렬하기 {boj}

TL;DR

작은 놈들부터 묶으면 비교 횟수가 줄어든다

source code

from typing import List
from heapq import heapify, heappush, heappop
from sys import stdin


def sol1(ls: List[int]) -> int:
    heapify(ls)
    res = 0
    while len(ls) > 0:
        pack1 = ls[0]
        heappop(ls)
        if len(ls) == 0:
            break
        pack2 = ls[0]
        heappop(ls)
        newpack = pack1 + pack2
        res += newpack
        heappush(ls, newpack)

    return res


if __name__ == "__main__":
    n = int(stdin.readline().strip())
    ls = [int(stdin.readline().strip()) for _ in range(n)]
    print(sol1(ls))